In statistical learning and analysis from shared data, which is increasingly widely adopted in platforms such as federated learning and meta-learning, there are two major concerns: privacy and robustness. Each participating individual should be able to contribute without the fear of leaking one's sensitive information. At the same time, the system should be robust in the presence of malicious participants inserting corrupted data. Recent algorithmic advances in learning from shared data focus on either one of these threats, leaving the system vulnerable to the other.

Formixtures of axis-aligned Gaussians, we show thateO(kd/ε2)samples suffice, matching a knownlowerbound.

For additional motivation, it is reasonable to consider Massart noise to be a more realistic model of real-life noise (even when benign) when compared to the RCN model, as it allows for some amount of non-uniformity. This made Definition 1 a possibly tractable way to relax the noise assumption, without running intotheaforementioned computational barriers foragnostic learning.

We give the first polynomial-time algorithm for robust regression in the listdecodable setting where an adversary can corrupt a greater than1/2 fraction ofexamples.

Given 2 (0,12] and 2 (0,1), letT bethesamplesetgiventothe learner.